package tencent

import "sort"

//超时
func threeSum(nums []int) [][]int {
	result := make([][]int, 0)
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		if nums[i] > 0 {
			break
		}
		for j := i + 1; j < len(nums)-1; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			if nums[i]+nums[j] > 0 {
				break
			}
			for k := len(nums) - 1; k > j; k-- {
				tmp := nums[i] + nums[j] + nums[k]
				if tmp == 0 {
					result = append(result, []int{nums[i], nums[j], nums[k]})
					break
				}
				//减枝
				if tmp > 0 {
					break
				}
			}
		}
	}
	return result
}
